iT邦幫忙

2022 iThome 鐵人賽

DAY 1
1
自我挑戰組

用C語言跑完LeetCode 75 - Part 1系列 第 1

[Day 01] 什麼是LeetCode 75? 以及 1480. Running Sum of 1d Array

  • 分享至 

  • xImage
  •  

前言

什麼是LeetCode?

LeetCode是一個求職者經常會使用的線上解題系統,LeetCode網站中的Study Plan提供了求職者經過主題分類後的題目整理,本次的主題就是Study Plan中的LeetCode 75。

什麼又是LeetCode 75?

LeetCode 75來源於Blind 75,Blind 75是由Facebook工程師 Yangshun 所發表的一組包含75道LeetCode題目的清單,最初發表於 Blind 社群,所以被很多人稱為:Blind 75,由於它幾乎涵蓋了演算法及資料結構中常見的知識點,非常適合想要快速掌握面試知識時拿來練習。

個人猜想LeetCode以Blind 75的題目為基礎設計了LeetCode 75,兩者題目選擇相似但並非完全相同,LeetCode 75是一個有三個等級(Level 1、Level 2及Level 3)的學習計畫(Study Plan),讓使用者每天進行2-3題;今年鐵人賽希望記錄用C語言走過LeetCode 75 Level 1的題目總共是30題 (20題Easy及10題Medium)。

  • 分享 Blind 75 作者 Yangshun 建立的新清單,有 75 題,分 5 週(五大主題)。
  • 分享作者 Yangshun 建立的網站,可以依個人每周投入的時間客製化學習計畫。

為什麼要使用C語言?

除了身為一個每天用C語言的韌體工程師以外,如果查詢網路上的解題資料,解答常常是以C++、Java或Python寫成,這些語言都有許多的容器和內建函數可以使用,用C語言沒有這些東西就會多了點自己造輪子的成就感。

接下來每天會如何進行?

每天會以LeetCode 75 Level 1中的一個題目作為對象,會針對題目做解釋和說明個人的想法、嘗試過的方向、經歷的錯誤等等,最後提供可通過的C語言程式碼。過程中也會參考網路上已有的解法,部分題目由於過於簡單導致篇幅會比較短,這時候就會從Level 2相同知識領域中拿一題來進行說明,所以每天會解答至少是一題至多是二題。

請問你是?

哈囉哈囉,大家好!我是Eric,一個韌體工程師,工作內容是撰寫車輛子系統的控制程式還有進行測試。
若系列文章中有錯字、寫錯或是有任何想討論的地方,請不吝留言告訴我!

第一天不是只有前言嗎? 第一週不是讓大家買書嗎?

由於計畫是30天進行30+題,所以第一天就要開始了!!


LeetCode 75 Level 1 - Day 1 Prefix Sum

1480. Running Sum of 1d Array題目

題目敘述

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.

預設函數

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* runningSum(int* nums, int numsSize, int* returnSize){

}

題目輸入限制

  • https://chart.googleapis.com/chart?cht=tx&chl=1%20%3C%3D%20nums.length%20%3C%3D%201000
  • https://chart.googleapis.com/chart?cht=tx&chl=-10%5E6%20%3C%3D%20nums%5Bi%5D%20%3C%3D%2010%5E6

解題過程

本題是 Day 1 Prefix Sum 中的第一題,主題都是輸入一個陣列,然後回傳計算好的值或是另一個陣列,這題非常容易,但是若是一開始接觸時,會不太了解題目中C語言預設函數的設定,後續題目也常常會遇到要處理陣列的輸入和輸出,以下進行說明:

  • 預設函數回傳值是輸出計算結果的陣列指標
  • 要先建立動態記憶體再回傳陣列指標,若是在函數內宣告靜態陣列在函數結束後就不存在了,無法傳遞出該陣列的指標
  • int* nums 是題目輸入要計算的陣列, numsSize 是該陣列的大小
  • int* returnSize 是要提供輸出陣列的大小
  • 記得 C 語言透過指標將陣列傳遞時都要再提供陣列的大小,不然對方只知道陣列的位置其實無法得知該陣列的大小

接下來由題目的敘述知道,我們只要把輸入陣列的第[i]項和第[i]項之前的值都加起來成為輸出陣列的第[i]項,如圖Fig. 2所示,輸出的第[i]項還可以寫成輸出的第[i - 1]項加上輸入的第[i]項

程式碼上傳

int* runningSum(int* nums, int numsSize, int* returnSize){
    int sum = 0;    
    int* dynArr = (int *)malloc(numsSize * sizeof(int));

    *dynArr = *nums;
    for (int i=1; i<numsSize; i++) {
        *(dynArr+i) = *(nums+i) + *(dynArr+i-1);
    }
    *returnSize = numsSize;  // 要回傳陣列的大小,和輸入陣列的大小相同
    return dynArr;
}

第一天就到這邊結束,謝謝大家。
/images/emoticon/emoticon08.gif


下一篇
[Day 02] LeetCode 75 - 724. Find Pivot Index
系列文
用C語言跑完LeetCode 75 - Part 130
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言